package 周赛._278;

/**
 * @author 会玩的洋洋
 * https://leetcode-cn.com/problems/find-substring-with-given-hash-value/
 */
public class _5994_查找给定哈希值的子串 {
    /**
     * 滑动窗口
     * @param s 字符串
     * @param power 需要多少平方
     * @param modulo 取余数值
     * @param k 限制字符数量
     * @param hashValue 对应的需要相等的hash值
     * @return String 获取到的字符串
     */
    public String subStrHash(String s, int power, int modulo, int k, int hashValue) {
        int n = s.length();
        for (int i = 0; i + k < n; i++) {
            String target = s.substring(i, i + k);
            if (checkHash(target, power, modulo, hashValue)) {
                return target;
            }
        }
        return s.substring(0, k);
    }
    public boolean checkHash(String target, int p, int m, int hashValue) {
        int n = target.length();
        long value = 0;
        for (int i = 0; i < n; i++) {
            char c = target.charAt(i);
            value = (long) ((c - 'a' + 1) * (Math.pow(p, i) % m) + value);
        }
        return value % m == hashValue;
    }
}
